package warm100;

public class productExceptSelf_238 {
    public int[] productExceptSelf(int[] nums) {
        //要求不要使用除法
        //思路是计算一组前缀乘积，一组后缀乘积
        int len=nums.length,f=1,b=1;
        int []left_multi=new int[len];
        int []right_multi=new int[len];
        int []ans=new int[len];
        for(int i=0;i<len;i++){
            f=f*nums[i];
            left_multi[i]=f;
        }
        for(int i=len-1;i>-1;i--){
            b=b*nums[i];
            right_multi[i]=b;
        }
        for(int i=0;i<len;i++){
            int left=1,right=1;
            left=i>0 ? left_multi[i-1] : 1;
            right=i<len-1 ? right_multi[i +1] :1;
            ans[i]=left*right;
        }
        return ans;
    }

    //优化空间复杂度
    public int[] productExceptSelf2(int[] nums) {
        int n = nums.length;
        int[] right = new int[n];
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] =right[i + 1] * nums[i + 1];  //算出每个位置后缀和（不包括当前位，便于后边计算）
        }

        int left = 1;
        for (int i = 0; i < n; i++) {
            // 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中
            right[i] *= left;   //先乘积，再更新left
            left *= nums[i];
        }

        return right;
    }

}
